package com.example.leetcode.sort;

import java.util.Arrays;

/**
 * @ClassName SelectSort
 * @Description 选择排序
 *  思路：第一次从[0...n-1]里的元素找到最小值，换到0处
 *      第二次从[1。。。n-1]里的元素找到最小值，换到1处
 *         。。。
 *      注意：内层循环的初始值，是i+1,因为外层循环每循环一次
 *      内层循环就少一次
 *
 * @Author liuzhihui
 * @Date 19/4/2021 下午 10:49
 * @Version 1.0
 **/
public class SelectSort {
    public static void main(String[] args) {
        int arr[]={3, 9, -1, 10, -2};
        System.out.println("排序前：" + Arrays.toString(arr));
        sort2(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }
    private static void sort(int[] nums){
        // 外层循环，次数为nums.length - 1,因为最多有nums.length - 1个元素需要排序
        for (int i = 0; i < nums.length - 1; i++) {
            //设置当前元素为最小值
            int min = nums[i];
            //记录最小值的索引
            int minIndex = i;

            //每次都选出当前循环的最小值
            for (int j =  i + 1; j < nums.length; j++){
                if (nums[j] < min){
                    min = nums[j];
                    minIndex = j;
                }
            }
            // 将最小值和前面的元素进行交换
            if (minIndex != i){
                nums[minIndex] = nums[i];
                nums[i] = min;
            }
        }
    }
    //练习
    private static void sort1(int[] nums){
        for (int i = 0; i < nums.length - 1; i++) {
            // 记录最小值
            int min = nums[i];
            // 记录最小的索引
            int minIndex = i;
            //找出当前循环的最小值
            // todo 这个初始值，注意，经常忘记
            for (int j = i + 1; j < nums.length; j++) {
                //找到最小值
                if (nums[j] < nums[minIndex]){
                    min = nums[j];
                    minIndex = j;
                }
            }
            //如果最小值不是当前值，就进行交换
            if(minIndex != i){
                nums[minIndex] = nums[i];
                nums[i] = min;
            }
        }
    }
    private static void sort2(int[] nums){
        for (int i = 0; i < nums.length - 1; i++) {
            int mid = nums[i];
            int minIndex = i;
            for (int i1 = i + 1; i1 < nums.length; i1++) {
                //找到比当前最小值，还小的元素
                if (nums[i1] < mid){
                    mid = nums[i1];
                    minIndex = i1;
                }
            }
            //交换
            nums[minIndex] = nums[i];
            nums[i] = mid;
        }
    }
}
